2799415
Using a compact tree to index and query XML data
Indexing XML is crucial for efficient XML query processing. We propose a compact tree (Ctree) for XML indexing, which provides not only concise path summaries at group level but also detailed child-parent relationships at element level. Based on Ctree, we are able to measure how well XML data is structured. We also propose a three-step query processing method. Its efficiency is achieved by: (1) summarizing large XML data structures into a condensed Ctree; (2) pruning irrelevant groups to significantly reduce the search space; (3) eliminating join operations between the matches for value predicates and those for structure constraints and (4) using Ctree properties such as regular groups to reduce query processing time. Our experiments reveal that Ctree is an effective data structure for managing XML data.
1275297
Bridging Physical and Virtual Worlds: Complex Event Processing for RFID Data Streams
Advances of sensor and RFID technology provide significant new power for humans to sense, understand and manage the world. RFID provides fast data collection with precise identification of objects with unique IDs without line of sight, thus it can be used for identifying, locating, tracking and monitoring physical objects. Despite these benefits, RFID poses many challenges for data processing and management: i) RFID observations contain duplicates, which have to be filtered; ii) RFID observations have implicit meanings, which have to be transformed and aggregated into semantic data represented in their data models; and iii) RFID data are temporal, streaming, and in high volume, and have to be processed on the fly. Thus, a general RFID data processing framework is needed to automate the transformation of physical RFID observations into the virtual counterparts in the virtual world linked to business applications. In this paper, we take an event-oriented approach to process RFID data, by devising RFID application logic into complex events. We then formalize the specification and semantics of RFID events and rules. We demonstrate that traditional ECA event engine cannot be used to support highly temporally constrained RFID events, and develop an RFID event detection engine that can effectively process complex RFID events. The declarative event-based approach greatly simplifies the work of RFID data processing, and significantly reduces the cost of RFID data integration.
227525
Integrated RFID data modeling: an approach for querying physical objects in pervasive computing
Radio frequency identiﬂcation(RFID) technology uses radio-frequency waves to transfer data between readers and mov-able tagged objects without line of sight. RFID holds thepromise of real-time identifying, locating, tracking and mon-itoring physical objects, and can be used for a wide range ofpervasive computing applications. To achieve these goals,RFID data have to be collected, transformed and expres-sively modeled as their virtual counterparts in the virtualworld. RFID data, however, have their own unique char-acteristics { including aggregation, location, temporal andhistory-oriented { which have to be fully considered and inte-grated into the data model. The diversity of RFID applica-tions pose further challenges to a generalized framework forRFID data modeling. In this paper, we explore the funda-mental characteristics of RFID data and classify RFID ap-plications into a set of typical scenarios. We then propose ageneralized RFID data modeling framework with constructsfor each typical scenario. These constructs can be combinedto model most RFID applications in real world.
5842197
Configurable indexing and ranking for XML information retrieval
Indexing and ranking are two key factors for efficient and effective XML information retrieval. Inappropriate indexing may result in false negatives and false positives, and improper ranking may lead to low precisions. In this paper, we propose a configurable XML information retrieval system, in which users can configure appropriate index types for XML tags and text contents. Based on users' index configurations, the system transforms XML structures into a compact tree representation, Ctree, and indexes XML text contents. To support XML ranking, we propose the concepts of "weighted term frequency" and "inverted element frequency," where the weight of a term depends on its frequency and location within an XML element as well as its popularity among similar elements in an XML dataset. We evaluate the effectiveness of our system through extensive experiments on the INEX 03 dataset and 30 content and structure (CAS) topics. The experimental results reveal that our system has significantly high precision at low recall regions and achieves the highest average precision (0.3309) as compared with 38 official INEX 03 submissions using the strict evaluation metric.
6631927
Ctree: a compact tree for indexing XML data
In this paper, we propose a novel compact tree (Ctree) for XML indexing, which provides not only concise path summaries at the group level but also detailed child-parent links at the element level. Group level mapping allows efficient pruning of a large search space while element level mapping provides fast access to the parent of an element. Due to the tree nature of XML data and queries, such fast child-to-parent access is essential for efficient XML query processing. Using group-based element reference, Ctree enables the clustering of inverted lists according to groups, which provides efficient join between inverted lists and structural index group extents. Our experiments reveal that Ctree is efficient for processing both single-path and branching queries with various value predicates.
11533048
RFID Data Processing with a Data Stream Query Language
RFID technology provides significant advantages over traditional object-tracking technologies and is increasingly adopted and deployed in real applications. RFID applications generate large volume of streaming data, which have to be automatically filtered, processed, and transformed into semantic data, and integrated into business applications. Indeed, RFID data are highly temporal, and RFID observations form complex temporal event patterns which can be very different for various RFID applications. Thus, it is desirable to have a general RFID data processing framework with a powerful language, for the end users to express a variety of queries on RFID data streams, as well as detecting complex events patterns. While data stream management systems (DSMSs) are emerging for optimized stream data processing, they usually lack the language construct support for temporal event detection. In this paper, we discuss a stream query language to provide comprehensive temporal event detection, through temporal operators and extension of sliding-window constructs. With the integration of temporal event detection, a DSMS has the capability to serve as a powerful system for RFID data processing.
16061427
A wide-field direction-selective aVLSI spiking neuron
We describe an analog Very-Large-Scale Integrated (aVLSI) wide-field direction-selective spiking neuron that responds robustly to both natural and artificial images. The circuitry is based on a model of the wide-field direction-selective neurons in the fly visual system. The architecture of the chip closely follows the anatomical layout of the fly visual system. The circuit has a one-dimensional array of 37 elementary motion detectors (EMDs); each of which provides local motion information to the wide-field spiking neuron. Normalisation and adaptation are employed in the circuits at each processing stage. The inputs to the EMDs saturate with high contrasts so that the motion output is not confounded with the signal contrast. The outputs of the EMDs are aggregated in a nonlinear way to produce a motion output that is independent of the stimulus size. The global aggregated signal is then used to drive an integrate-and-fire neuron. All the computation is analog except for the output of the spiking neuron. We show results from the fabricated circuit.
5840503
Silicon Retina with Adaptive Filtering Properties
This paper describes a small, compact circuit, the retino-laminar (RL) circuit, that captures the temporal and adaptation properties both of the photoreceptor and of the laminar layers of the fly. The RL circuit uses only six transistors and two capacitors. The circuit is operated in the subthreshold domain; it has a low DC gain and a high transient gain. The adaptation time constant of the RL circuit can be controlled via an external bias. Its temporal filtering properties change with the background intensity and with the signal-to-noise ratio. The frequency response of the circuit shows that, in the frequency range of 1 to 100 Hz, the circuit response goes from highpass filtering under high light levels to lowpass filtering under low light levels (i.e., when the signal-to-noise ratio is low).
2805433
On the Potential of Structure-Free Data Aggregation in Sensor Networks
Data aggregation protocols can reduce the cost of communication, thereby extending the lifetime of sensor networks. Prior work on data aggregation protocols has focused on tree-based or cluster-based structured approaches. Although structured approaches are suited for data gathering applications, they incur high maintenance overhead in dynamic scenarios for event-based applications. The goal of our work is to design techniques and protocols that lead to efficient data aggregation without explicit maintenance of a structure. As packets need to converge spatially and temporally for data aggregation, we propose two corresponding mechanisms Data-Aware Anycast at the MAC layer and Randomized Waiting at the application layer. We model the performance of the combined protocol that uses both the approaches and show that our analysis matches with the simulations. Using extensive simulations and experiments on a testbed with implementation in TinyOS, we study the performance and potential of structure-free data aggregation.
11183356
Consequences for exchange energy density functional of exponentially decaying nature of atomic electron densities
2425320
Scalable data aggregation for dynamic events in sensor networks
Computing and maintaining network structures for efficient data aggregation incurs high overhead for dynamic events where the set of nodes sensing an event changes with time. Moreover, structured approaches are sensitive to the waiting-time which is used by nodes to wait for packets from their children before forwarding the packet to the sink. Although structureless approaches can address these issues, the performance does not scale well with the network size. We propose a semi-structured approach that uses a structureless technique locally followed by Dynamic Forwarding on an implicitly constructed packet forwarding structure to support network scalability. The structure, ToD, is composed of multiple shortest path trees. After performing local aggregation, nodes dynamically decide the forwarding tree based on the location of the sources. The key principle behind ToD is that adjacent nodes in a graph will have low stretch in one of these trees in ToD, thus resulting in early aggregation of packets. Based on simulations on a 2000 nodes network and real experiments on a 105 nodes Mica2-based network, we conclude that efficient aggregation in large scale networks can be achieved by our semi-structured approach.