BINRANK: Dynamic authority-based keyword search algorithm

Dynamic authority-based keyword search algorithms, such as Object Rank and personalized PageRank, leverage semantic link information to provide high quality, high recall search in databases, and the Web. Conceptually, these algorithms require a  querytime PageRank-style iterative computation over the full graph. This computation is too expensive for large graphs and not feasible at query time. Alternatively, building an index of precomputed results for some or all keywords involves very expensive   preprocessing. We introduce BinRank, a system that approximates ObjectRank results by utilizing a hybrid approach inspired by materialized views in traditional query processing. We materialize a number of relatively small subsets of the data graph in such a way that any keyword query can be answered by running ObjectRank on only one of the subgraphs. BinRank generates the subgraphs by partitioning all the terms in the corpus based on their co-occurrence, executing ObjectRank for each partition using the terms to generate a set of random walk starting points, and keeping only those objects that receive non-negligible scores. The intuition is that a subgraph that contains all objects and links relevant to a set of related terms should have all the information needed to rank objects with respect to one of these terms. 

More >> BINRANK: Dynamic authority-based keyword search algorithm