Converting unordered graphs to oblivious read once ordered graph representation
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/00
G06N-005/02
출원번호
US-0206514
(2008-09-08)
등록번호
US-8280836
(2012-10-02)
발명자
/ 주소
Kumar, Prasun
출원인 / 주소
Fair Isaac Corporation
대리인 / 주소
Mintz, Levin, Cohn, Ferris, Glovsky and Popeo, P.C.
인용정보
피인용 횟수 :
1인용 특허 :
76
초록▼
Data characterizing a desired variable order and an unordered graph can be received so that all paths in the unordered graph can be enumerated and a first path in the unordered graph can be leveled according to the desired variable order in a first oblivious read once decision graph. For each additi
Data characterizing a desired variable order and an unordered graph can be received so that all paths in the unordered graph can be enumerated and a first path in the unordered graph can be leveled according to the desired variable order in a first oblivious read once decision graph. For each additional path other than the first path, the additional path is leveled in the desired order, nodes of the additional path are added to the first oblivious read once decision graph, and a union operation is performed on the first oblivious read once decision graph to union graph roots on the first oblivious read once decision graph. Thereafter, generation of a second oblivious read once decision graph can be initiated after completing processing of the first path and each additional path. Related apparatus, systems, techniques and articles are also described.
대표청구항▼
1. An article comprising a tangible machine-readable storage medium embodying instructions that when performed by one or more machines result in operations comprising: receiving data characterizing a desired variable order and an unordered graph;enumerating all paths in the unordered graph;leveling,
1. An article comprising a tangible machine-readable storage medium embodying instructions that when performed by one or more machines result in operations comprising: receiving data characterizing a desired variable order and an unordered graph;enumerating all paths in the unordered graph;leveling, in an oblivious read once decision graph, a first path in the unordered graph according to the desired variable order; andfor each additional path in the unordered graph other than the first path, leveling the additional path in the desired order, adding nodes of the additional path to the oblivious read once decision graph, and performing a union operation on the oblivious read once decision graph to union graph roots on the oblivious read once decision graph. 2. An article as in claim 1, wherein each additional path added to the first oblivious read once decision graph is in a conjunctive normal form. 3. An article as in claim 1, wherein the first path is leveled in an empty oblivious read once decision graph. 4. An article as in claim 1, wherein the storage medium further embodies instructions that when performed by one or more machines result in operations comprising: for each additional path, iterating each node in bottom up order to determine if same node already exists in the oblivious read once decision graph. 5. An article as in claim 4, wherein the storage medium further embodies instructions that when performed by one or more machines result in operations comprising: adding a new node to the oblivious read once decision graph if is determined that such node does not already exist. 6. An article as in claim 4, wherein two nodes are considered same if corresponding node conditions and sub-graph below the two nodes are identical. 7. An article as in claim 6, wherein hashing techniques are used to identify isomorphic sub-graphs. 8. An article as in claim 1, wherein adding nodes for each additional path results in two root nodes in the oblivious read once decision graph, and wherein the union operation merges two root nodes and child nodes reachable from the root nodes such that there is only one root node in the oblivious read once decision graph and the child conditions of a parent are not overlapping. 9. An article as in claim 8, wherein the merging is performed such that any two nodes having the same subgraph are replaced with a new node with a condition that is union of the conditions of the replaced nodes. 10. An article as in claim 1, wherein the paths are enumerated by a depth first traversal. 11. A computer-implemented method comprising: receiving data characterizing a desired variable order and an unordered graph;enumerating all paths in the unordered graph;leveling, in an oblivious read once decision graph, a first path in the unordered graph according to the desired variable order; andfor each additional path in the unordered graph other than the first path, leveling the additional path in the desired order, adding nodes of the additional path to the oblivious read once decision graph, and performing a union operation on the oblivious read once decision graph to union graph roots on the oblivious read once decision graph. 12. A method as in claim 11, wherein each additional path added to the first oblivious read once decision graph is in a conjunctive normal form. 13. A method as in claim 11, wherein the first path is leveled in an empty oblivious read once decision graph. 14. A method as in claim 11 further comprising: for each additional path, iterating each node in bottom up order to determine if same node already exists in the oblivious read once decision graph. 15. A method as in claim 14 further comprising: adding a new node to the oblivious read once decision graph if is determined that such node does not already exist. 16. A method as in claim 14, wherein two nodes are considered same if corresponding node conditions and sub-graph below the two nodes are identical. 17. A method as in claim 16, wherein hashing techniques are used to identify isomorphic sub-graphs. 18. A method as in claim 11, wherein adding nodes for each additional path results in two root nodes in the oblivious read once decision graph, and wherein the union operation merges two root nodes and child nodes reachable from the root nodes such that there is only one root node in the oblivious read once decision graph and the child conditions of a parent are not overlapping. 19. A method as in claim 18, wherein the merging is performed such that any two nodes having the same subgraph are replaced with a new node with a condition that is union of the conditions of the replaced nodes. 20. A method as in claim 11, wherein the paths are enumerated by a depth first traversal. 21. An article comprising a non-transitory machine-readable storage medium embodying instructions that when performed by one or more machines result in operations comprising: receiving data characterizing a desired variable order and an unordered graph;enumerating all paths in the unordered graph; andrecursively leveling, for an oblivious read once decision graph, each enumerated path according to the desired variable order. 22. An article as in claim 21, wherein the storage medium further embodies instructions that when performed by one or more machines result in operations comprising: combining root nodes of the oblivious read once decision graph.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (76)
Boyle Valerie Y. (Wheaton IL) Lu Daryl C. (Freehold NJ) Sicherman George L. (Ocean NJ) Swanson Robert A. (Naperville IL), Apparatus to manipulate and examine the data structure that supports digit analysis in telecommunications call processin.
Huang Ying ; Desiraju Ramakrishna ; Begue Christophe ; Bakkalbasi Omer ; Chan Lap Mui Ann ; Bhaskaran Krishnakumar ; Federgruen Awi ; Krasinski Raymond J. ; Boey Peter, Decision support system for the management of an agile supply chain.
Turpin William M. (Santa Cruz CA) Brown Kevin L. (Scotts Valley CA) Bogrett Steven W. (Campbell CA), Development system with methods for maintaining data integrity of information stored as a data record in a database with.
Turpin William Monroe ; Brown Kevin Lane ; Bogrett Steven Ward, Graphical programming system and methods for assisting a user with creating screen objects on a screen device.
Amado Carlos Armando (444 Brickell Avenue #51-111 Miami FL 33131-2400), Method and apparatus for applying if-then-else rules to data sets in a relational data base and generating from the resu.
Strasnick Steven L. (Mountain View CA) Tesler Joel D. (Cupertino CA), Method and apparatus for displaying data within a three-dimensional information landscape.
Bereiter Thomas William ; Gan Doron, Method and system for displaying an expandable tree structure in a data processing system graphical user interface.
Kleinberg Jon Michael, Method and system for identifying authoritative information resources in an environment with content-based links between information resources.
Simoudis Evangelos (San Mateo CA) Livezey Brian K. (Menlo Park CA) Kerber Randy G. (San Jose CA), Method for generating predictive models in a computer system.
Kiernan Casey L. (Redmond WA) Jancke Gavin (Redmond WA), Method for separating a hierarchical tree control into one or more hierarchical child tree controls in a graphical user.
Altschuler, Steven; Ingerman, David V.; Wu, Lani; Zhao, Lei, Methods and apparatus for finding semantic information, such as usage logs, similar to a query using a pattern lattice data space.
Ebert Justin C. ; Collins Scott H. ; Arnold John P. ; David Stephen L. ; Dwyer Susan D. ; Mills Michael D. ; Shanahan Patricia, Project organization and optimization tool and method of use thereof.
de l'Etraz Paris,ESX ; Fees James R.,BEX ; Hatcher Paul,GBX ; Bruderer Otto,CHX ; Fees Christina M.,GBX, System, method, and computer program product for providing relational patterns between entities.
Fox Frederick D. ; Pearson Douglas R. ; Caine Diane ; Kenney Andrew ; Morris Richard A.,GB2 ; Beck Steve A. ; Beck Cathy J. ; Chu Robert J., User interface for graphically displaying the impact of weather on managerial planning.
Colett, Hannah R.; Corriveau, Philip J.; Doherty, Rina A.; Scovell, James J.; Han, Sarah Jihye; Guo, Yinni; Szostak, Dalila, System and method for electronically tagging items for use in controlling electrical devices.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.