NDLI: XPath query evaluation based on the stack encoding

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

CINDI: a digital library for academics

Anonymizing location-based RFID data

Agile development: issues and avenues requiring a substantial enhancement of the business perspective in large projects

A type system for hybrid intensional-imperative programming support in GIPSY

Markovian workload modeling for Enterprise Application Servers

CPU, SMP and GPU implementations of Nohalo level 1, a fast co-convex antialiasing image resampler

An automated procedure for identifying poorly documented object oriented software components

A local algorithm for dominating sets of quasi-unit disk graphs

Broadcasting in necklace graphs

An adaptive multi-strategy approach for semantic mapping

The promise of solid state disks: increasing efficiency and reducing cost of DBMS processing

Bridging the gap: Discrete-Event Systems for software engineering (short position paper)

A verification framework for access control in dynamic web applications

Radius selection algorithms for sphere decoding

Texture map: an effective representation for image segmentation

Edit metric decoding: a new hope

Impediments to general purpose Content Based Image search

Issues in pattern mining and their resolutions

XPath query evaluation based on the stack encoding

Integrating heterogeneous user interfaces in service oriented web applications

ACDL: a communication choreography for discrete step multi-agent social simulations

Autonomic specification of self-protection for distributed MARF with ASSL

Use of semantic web technology for adding 3D detail to GIS landscape data

General spanning trees and reachability query evaluation

Option pricing using Particle Swarm Optimization

Network survivability in large-scale regional failure scenarios

An ASSL-generated architecture for autonomic systems

Application of advanced rendering and animation techniques for 3D games to softbody modeling and animation

Component placement and location for a dynamic software composition system

Designing an interactive OpenGL slide-based presentation of the softbody simulation system for teaching and learning of computer graphics techniques

Integrating usability engineering and software engineering in mixed reality system development

Modeling for dynamic aspect-oriented development

Real-time haptic display of fluids

ConfSys2: an improved web-based multi-conference management system

XPath query evaluation based on the stack encoding

Content Provider	ACM Digital Library
Author	Chen, Yangjun Cooke, Donovan
Abstract	The twig join, which is used to find all occurrences of a twig pattern in an XML database, is a core operation for XML query processing. A great many strategies for handling this problem have been proposed and can be roughly classified into two groups. The first group decomposes a twig pattern (a small tree) into a set of binary relationships between pairs of nodes, such as parent-child and ancestor-descendant relations; and transforms a tree matching problem into a series of simple relation look-ups. The second group decomposes a twig pattern into a set of paths. Among all this kind of methods, the approach based on the so-called stack encoding by Bruno et. al. [2] is very interesting, which can represent in linear space a potentially exponential (in the number of query nodes) number of matching paths. However, the available processes for generating such compressed paths suffer some redundancy and can be significantly improved. In this paper, we analyze this method and show that the time complexities of path generation in its two main procedures: PathStack and TwigStack can be reduced from $O(m^{2}$ ·n) to O(m ·n), where m and n are the sizes of the query tree and document tree, respectively. Experiments have been done to compare ours and some existing startegies, which shows that using our method much less time is needed to generate matching paths.
Starting Page	43
Ending Page	57
Page Count	15
File Format	PDF
ISBN	9781605584010
DOI	10.1145/1557626.1557634
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-05-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Trees Twig joins Xml pattern matching Paths Xml databases
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