NDLI: Challenges in selecting paths for navigational queries: trade-off of benefit of path versus cost of plan

Please wait, while we are loading the content...

Text Centric Structure Extraction and Exploitation (abstract only)

Spam, damn spam, and statistics: using statistical analysis to locate spam web pages

One torus to rule them all: multi-dimensional queries in P2P systems

Scalable dissemination: what's hot and what's not

Twig query processing over graph-structured XML data

Challenges in selecting paths for navigational queries: trade-off of benefit of path versus cost of plan

DTDs versus XML schema: a practical study

Querying bi-level information

Querying peer-to-peer networks using P-trees

Semantic multicast for content-based stream dissemination

Unraveling the duplicate-elimination problem in XML-to-SQL query translation

Content and structure in indexing and ranking XML

On validation of XML streams using finite state machines

Visualizing and discovering web navigational patterns

Best-match querying from document-centric XML

Mining approximate functional dependencies and concept similarities to answer imprecise queries

Checking potential validity of XML documents

Challenges in selecting paths for navigational queries: trade-off of benefit of path versus cost of plan

Content Provider	ACM Digital Library
Author	Mestre, Julian Vidal, María-Esther Raschid, Louiqa
Abstract	Life sciences sources are characterized by a complex graph of overlapping sources, and multiple alternate links between sources. A (navigational) query may be answered by traversing multiple alternate paths between a start source and a target source. Each of these paths may have dissimilar benefit, e.g., the cardinality of result objects that are reached in the target source. Paths may also have dissimilar costs of evaluation, i.e., the execution cost of a query evaluation plan for a path. In prior research, we developed ESearch, an algorithm based on a Deterministic Finite Automaton (DFA), which exhaustively enumerates all paths to answer a navigational query. The challenge is to develop heuristics that improve on the exhaustive ESearch solution and identify good utility functions that can rank the sources, the links between sources, and the sub-paths that are already visited, in order to quickly produce paths that have the highest benefit and the least cost. In this paper, we present a heuristic that uses local utility functions to rank sources, using either the benefit attributed to the source, the cost of a plan using the source, or both. The heuristic will limit its search to some Top XX% of the ranked sources. To compare ESearch and the heuristic, we construct a Pareto surface of all dominant solutions produced by ESearch, with respect to benefit and cost. We choose the Top 25% of the ESearch solutions that are in the Pareto surface. We compare the paths produced by the heuristic to this Top 25% of ESearch solutions with respect to precision and recall. This motivates the need for further research on developing a more efficient algorithm and better utility functions.
Starting Page	61
Ending Page	66
Page Count	6
File Format	PDF
DOI	10.1145/1017074.1017091
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-17
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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