NDLI: BinRank: Scaling Dynamic Authority-Based Search Using Materialized SubGraphs

Content Provider	IEEE Xplore Digital Library
Author	Heasoo Hwang Balmin, A. Reinwald, B. Nijkamp, E.
Copyright Year	2009
Abstract	Dynamic authority-based keyword search algorithms, such as ObjectRank and personalized PageRank, leverage semantic link information to provide high quality, high recall search in databases and the Web. Conceptually, these algorithms require a query-time 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 pre-computed 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 sub-graphs. BinRank generates the sub-graphs 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 sub-graph 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. We demonstrate that BinRank can achieve sub-second query execution time on the English Wikipedia dataset, while producing high quality search results that closely approximate the results of ObjectRank on the original graph. The Wikipedia link graph contains about 10^8 edges, which is at least two orders of magnitude larger than what prior state of the art dynamic authority-based search systems have been able to demonstrate. Our experimental evaluation investigates the trade-off between query execution time, quality of the results, and storage requirements of BinRank.
Starting Page	66
Ending Page	77
File Size	483636
Page Count	12
File Format	PDF
ISBN	9781424434220
ISSN	10844627
DOI	10.1109/ICDE.2009.94
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-03-29
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Databases Wikipedia Web pages Keyword search Iterative algorithms Scalability Dictionaries Data engineering Query processing Social network services
Content Type	Text
Resource Type	Article
Subject	Signal Processing Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Effective Bin Rank for Scaling Dynamic Authority Based Search with Materialized Sub Graphs

Approximate Keyword Search in Web Search Engines

Holistic Query Transformations for Dynamic Web Applications

WISE: A Workflow Information Search Engine

Visualized Elucidations of Ranking by Exploiting Object Relations

WEST: Modern Technologies for Web People Search

E-Business Social Network Optimization and Visualization

Reachability Indexes for Relational Keyword Search

Scalable Keyword Search on Large Data Streams

BinRank: Scaling Dynamic Authority-Based Search Using Materialized SubGraphs

Similar Documents

Effective Bin Rank for Scaling Dynamic Authority Based Search with Materialized Sub Graphs

Approximate Keyword Search in Web Search Engines

Holistic Query Transformations for Dynamic Web Applications

WISE: A Workflow Information Search Engine

Visualized Elucidations of Ranking by Exploiting Object Relations

WEST: Modern Technologies for Web People Search

E-Business Social Network Optimization and Visualization

Reachability Indexes for Relational Keyword Search

Scalable Keyword Search on Large Data Streams

BinRank: Scaling Dynamic Authority-Based Search Using Materialized SubGraphs