System and method for ranked keyword search on graphs
US7702620B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 29, 2007 |
| Grant date | Apr 20, 2010 |
| Priority date | — |
| Expiry date | Dec 2, 2027 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99933
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Arrangements and methods for providing for the efficient implementation of ranked keyword searches on graph-structured data. Since it is difficult to directly build indexes for general schemaless graphs, conventional techniques highly rely on graph traversal in running time. The previous lack of more knowledge about graphs also resulted in great difficulties in applying pruning techniques. To address these problems, there is introduced herein a new scoring function while the block is used as an intermediate access level; the result is an opportunity to create sophisticated indexes for keyword search. Also proposed herein is a cost-balanced expansion algorithm to conduct a backward search, which provides a good theoretical guarantee in terms of the search cost.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.