Search

The systematic Brain Informatics (BI) study is a data-driven process and all decision-making and suppositions depend on the deep understanding of brain data. Aiming at unstructured brain data, semantic neuroimaging data provenances, called BI provenances, have been constructed to support the quick and comprehensive understanding about data origins and data processing. However, the existing file-based or transaction-database-based provenance queries cannot effectively meet the requirements of understanding data and generating decision or suppositions in the systematic study, which needs multi-aspect and multi-granularity information of provenances. Inspired by the online analytical processing (OLAP) system, this paper proposes provenance cubes to support multi-aspect and multi-granularity provenance queries. A Data-Brain based approach is also designed to develop a BI OLAP system based on provenances cubes. The case study demonstrates significance and usefulness of the proposed approach.

Location-based services (LBS) have became more and more popular nowadays since people equipped with smart phones. Existing keyword k-nearest neighbor (kNN) search methods focus more on the keywords; therefore, they use direct distance of two points, also known as, Euclidean distance as spatial constraints. However, the nearest point-of-interest (POI) returned by these services may not be the nearest on the road networks. For some services that consider the road networks, they use road expansion methods to solve this problem. The speed limitation for a large road network and index structures for millions POI may be the bottlenecks for these services. To address those problems, we develop a fast keyword kNN search system in road networks, called Saturn. Instead of using road expansion methods, we introduce a grid-based shortest path computation method, a filter-and-verification framework to search fast in road networks, and we also devise an improvement of the grid index to further improve the performance. We conduct extensive experiments on real data sets, and the experimental results show that our method is efficient and scalable to large data sets, significantly outperforming state-of-the-art methods.

As the foundation of location-based services, accurate localization has attracted considerable attention. A typical wi-fi localization system employs a fingerprint-based method, which constructs a fingerprint database and returns user’s location based on similar fingerprints. Existing systems cannot accurately locate users in a metropolitan-scale because of the requirement of large fingerprint data sets, complicated deployment, and the inefficient search algorithm. To address these problems, we develop a localization system called Polaris. By the contribution of users, we construct a large fingerprint database. We introduce an effective localization model based on novel similarity measures of fingerprints. For fast localization, we devise an efficient algorithm for matching similar fingerprints, and develop a cluster-based representative fingerprint selection method to improve the performance. We conduct extensive experiments on real data sets, and the experimental results show that our method is accurate and efficient, significantly outperforming state-of-the-art methods.

Flash memory has been widely used as secondary storage in many systems, such as mobile devices, portable computers and enterprise servers. However, due to the unique characteristics of flash memory, the optimization of flash-based systems for exploiting the superior properties as well as overcoming the limitations of flash memory becomes an important and challenging problem. In this paper, we propose page-level log mapping to address this problem. It adopts backward link technique to optimize the logical-to-physical page mapping, which can improve the read and write performance of flash-based systems. It also incorporates flash-optimized policies for buffer management, free page allocation and garbage collection. Experimental results show that our approach achieves high efficiency across a wide range of workloads, flash types and memory constraints, and significantly outperforms state-of-the-art methods.

Data distortion is inevitable in privacy-preserving data publication and a lot of quality metrics have been proposed to measure the quality of anonymous data, where information loss metrics are popularly used. Most of existing information loss metrics, however, are non-semantic and hence are limited in reflecting the data distortion. Thus, the utility of anonymous data based on these metrics is constrained. In this paper, we propose a novel semantic information loss metric SILM, which takes into account the correlation among attributes. This new metric can capture the distortion more precisely than the state of art information loss metrics especially for the scenario where strong correlations exist among attributes. We evaluated the effect of SILM on data quality in terms of the accuracy of aggregate query answering and classification. Comprehensive experiments demonstrate that SILM can help improve the quality of anonymous data much more especially if integrated with proper anonymization algorithms.

Multi-cores are more and more popular recently and have being altered the course of computing. Traditional XPath query evaluation algorithms cannot take full advantages of multi-cores, and it is not straightforward to adapt such algorithms on multi-cores. In this paper, we propose an efficient parallel PathStack algorithm, named P-PathStack, for processing XML twig queries. The algorithm first efficiently partitions input element lists into multiple buckets, and then processes data in each bucket in parallel. With efficient partitioning method, our proposed algorithm can avoid many useless elements and achieve very good speedup ratio. We have implemented the algorithm and experimental results show that it achieves high performance and speedup ratio.

Aiming at ensuring privacy preservation in personal data publishing, the topic of anonymization has been intensively studied in recent years. However, existing anonymization techniques all assume each tuple in the microdata table contains one single sensitive attribute (the SSA case), while none paid attention to the case of multiple sensitive attributes in a tuple (the MSA case). In this paper, we conduct the pioneering study on the MSA case, and propose a new framework, decomposition, to tackle privacy preservation in the MSA case.

Nowadays a huge amount of data were automatically generated or extracted from other data sources. The uncertainty and imprecision are intrinsic in those data. In this paper, we study the problem of effective keyword search over uncertain data. We allow approximate matching between input keywords and the strings in the underlying data, even in the presence of minor errors of input keywords. We formalize the problem of fuzzy keyword search over uncertain data. We propose efficient algorithms, effective ranking functions, and early-termination techniques to facilitate fuzzy keyword search over uncertain data. We propose a lattice based fuzzy keyword search method to efficiently identify top-k answers. Extensive experiments on a real dataset show that our proposed algorithm achieves both high result quality and search efficiency.

To reduce the risk of privacy disclosure during personal data publishing, the approach of anonymization is widely employed. On this topic, current studies mainly focus on two directions: (1)developing privacy preserving models which satisfy certain constraints, such as k-anonymity, l-diversity, etc.; (2)designing algorithms for certain privacy preserving model to achieve better privacy protection as well as less information loss. This paper generally belongs to the second class. We introduce an effective algorithm "BSGI" for the widely accepted privacy preserving model: l-diversity. In the meantime, we propose a novel interpretation of l-diversity: Unique Distinct l-diversity, which can be properly achieved by BSGI. We substantiate it's a stronger l-diversity model than other interpretations. Related to the algorithm, we conduct the first research on the optimal assignment of parameter laccording to certain dataset. Extensive experimental evaluation shows that Unique Distinct l-diversity provides much better protection than conventional l-diversity models, and BSGIgreatly outperforms the state of the art in terms of both efficiency and data quality.

Tree-structured data are becoming ubiquitous nowadays and manipulating them based on similarity is essential for many applications. Although similarity search on textual data has been extensively studied, searching for similar trees is still an open problem due to the high complexity of computing the similarity between trees, especially for large numbers of tress. In this paper, we propose to transform tree-structured data into strings with a one-to-one mapping. We prove that the edit distance of the corresponding strings forms a bound for the similarity measures between trees, including tree edit distance, largest common subtrees and smallest common super-trees. Based on the theoretical analysis, we can employ any existing algorithm of approximate string search for effective similarity search on trees. Moreover, we embed the bound into a filter-and-refine framework for facilitating similarity search on tree-structured data. The experimental results show that our algorithm achieves high performance and outperforms state-of-the-art methods significantly. Our method is especially suitable for accelerating similarity query processing on large numbers of trees in massive datasets.

The existing approaches of keyword search over relational databases usually first generate all possible results composed of relevant tuples and then sort them based on their individual ranks. These traditional methods are inefficient to identify the top-kanswers with the highest ranks. This paper studies the problem of progressively identifying the top-kanswers from the relational databases. The approach of progressively identifying the answers is very desirable as it generates the higher ranked results earlier thereby reducing the delay in responding to the user query. We have implemented our proposed method, and the experimental results show that our method outperforms existing state-of-the-art approaches and achieves much better search performance.

The existing approaches of keyword search over relational databases always identify the relationships between tuples on the fly, which are rather inefficient as such relational relationships are very rich in the underlying databases. Alternatively, this paper proposes an alternative way by retrieving and materializing tuple units for facilitating the online processing of keyword search. We first propose a novel concept of tupleunits, which are composed of the relevant tuples connected by the primary-foreign-key relationships. We then demonstrate how to generate and materialize the tuple units, and the technique for generating the tuple units can be done by issuing SQL statements and thus can be performed directly on the underlying RDBMS without modification to the database engine. Finally, we examine the techniques of indexing and ranking to improve the search efficiency and search quality. We have implemented our method and the experimental results show that our approach achieves much better search performance, and outperforms the alternative literatures significantly.

Finding all the occurrences of a twig pattern on multiple elements in an XML document is a core operation for efficient evaluation of XML queries. Holistic twig join algorithms, TwigStack and TSGeneric, have been recognized as optimal solutions when the twig pattern only involves A-D(ancestordescendant) relationships, while iTwigJoin can be optimal for partial twig patterns that contain A-D only or P-C (parent-child) only relationships. However, existing algorithms involve unnecessary computations and CPU cost of them can be further improved, and we in this paper mainly address this problem. We first propose three effective optimization rules to avoid those unnecessary computations, and then present two algorithms incorporated with these optimization rules to effectively answer twig patterns in leaf-to-root combining with root-to-leaf way. Experimental results on various datasets indicate that our algorithms perform significantly better than existing proposals.

We in this paper investigate keyword search over data-centric XML documents. We first present a novel method to divide an XML document into self-integrated subtrees, which are connected subtrees and can capture different structural information of the XML document. We then propose the meaningful self-integrated trees, which contain all the keywords and describe how the keywords are interrelated, to answer keyword search over XML documents. In addition, we introduce the B+-tree index to accelerate the retrieval of those meaningful self-integrated trees. Moreover, to further enhance the performance of keyword search, we present Bloom Filter to improve the efficiency of generating those meaningful self-integrated trees. Finally, we conducted extensive experiments to evaluate the performance of our method, and the experimental results demonstrate that our method achieves high efficiency and outperforms the existing approaches significantly.

As a query language for navigating XML trees and selecting a set of element nodes, XPath is ubiquitous in XML applications. One important issue of XPath queries is checking containment. In particular, we investigate a frequently used fragment of XPath that consists of node tests, the child axis (/), the descendant axis (//), branches ([]) and label wildcards (*). For special classes of pattern trees, the homomorphism algorithm returns false negatives. In order to address this problem, we propose two containment techniques, conditioned homomorphism and hidden conditioned homomorphism, and then present sound algorithms to check containment. The analytical result is given with an experiment.

Maintaining a semantic cache of materialized XPath views inside or outside the database, is a novel, feasible and efficient approach to accelerate XML query processing. However, the main problems of existing approaches are that, they either can not exploit sufficient potential cached views to answer an issued query or need too much time for cache lookup. In this paper, we propose, SCEND, an efficient Semantic Cache based on dEcompositioN and Divisibility, which adequately explores the answerability of views, and speeds up cache lookup dramatically. We decompose complex XPath queries into some much simpler and tractable ones to improve cache hit rate, moreover, we introduce a notion of the divisibility between two positive integers to accelerate cache lookup. In addition, we present a new replacement technique for SCEND to improve performance for caching. We experimentally demonstrate the efficiency of our caching techniques and performance gains obtained by employing such a cache.

High performance of query processing in large scale graph-structured data poses a pressing demand for high-quality statistics collection and selectivity estimation. Precise and succinct statistics collection about graph-structured data plays a crucial role for graph query selectivity estimation. In this paper, we propose the approach SMT, Succinct Markov Table, which achieves high precision in selectivity estimation with low memory space consumed. Four core notions of SMT are constructing, refining, compressing and estimating. The efficient algorithm SMTBuilder provides facility to build adaptive statistics model in the form of SMT. Versatile optimization rules, which investigate local bi-directional reachability, are introduced in SMT refining. During compressing, affective SMT grouping techniques are introduced. Statistical methods are used for selectivity estimations of various graph queries basing on SMT, especially for twig queries. By a thorough experimental study, we demonstrate SMT's advantages in accuracy and space by comparing with previously known alternative, as well as the preferred optimization rules and compressing technique that would favor different real-life data.

Visualization is able to present the rich Web information intuitively and make the Web search/mining more productive. Mobile computing is able to provide the flexibility of working anytime and anywhere. Therefore, it is natural to combine the two techniques for intriguing applications. However, the technical limitations of mobile devices make it difficult to port well-designed visualization methods from desktop computers to mobile devices. In this paper, we present what we learned on engineering 3D Web visualization on both high-end and low-end mobile devices as the MWeb3D framework, which forms a distributed pipeline that move intensive computation from the mobile devices to server systems. Some important issues of this strategy include: (1) separating visualization from graphics rendering, (2) encoding visual presentation for transmitting via bandwidth-limited wireless connections, (3) user interaction on mobile devices, and (4) highly efficient graphics rendering on the mobile devices. We will show fruitful experiments on both PDA and mobile phone with photos taken from both simulator and real mobile devices.

Speeding up query evaluation in large XML repositories becomes a challenging and all-important problem with vast XML-related applications arising. In this paper, we present SCALER, an efficient algorithm for XML query answering based on UDFTS and effective twig structure matching scheme. UDFTS not only constructs a one-to-one correspondence between trees and sequences but also maintains critical parent-child relationships for twig structure matching. With SCALER, XML queries can be performed by subsequence matching without breaking twigs into sub paths and evaluating these paths individually. Thus, costly join operations can be avoided elegantly. We also show the correctness of query answering by eliminating false dismissals and false alarms naturally in SCALER. By a thorough experimental study on various real-life data, we prove the efficiency and scalability of SCALER over the previous known alternative.

The identification of parent-child or ancestor-descendant relationship between XML elements plays a crucial role in efficient XML query processing. One popular method is to code each node in the XML document tree. However, its main problem is that either lacks the ability to support XML documents update or need huge storage space. This paper proposes a new update-supporting coding scheme based on binary-tree to identify the ancestor-descendant relationship or the parent-child relationship in constant time bound, which also effectively supports XML documents update. To reduce the coding space, we then propose a new storage approach, Blocked Binary-Tree Coding scheme (BBTC), whose average code length reduces to O(log(n)). Our extensive experiments show that BBTC significantly outperforms previous ones.

We propose a new approach to discover and extract topic-specific hypertext resources from the WWW. The method, called schema driven and topical crawling, allows a user to define schema and extracting rules for a specific domain of interests. It supports automatically search and extract schema-relevant web pages from the web. Different from common approaches that surf solely on web pages, our approach supports crawler to surf on a virtual network composed by concept instances and relationships. To achieve such a goal, we design an architecture that integrates several techniques including web extractor, meta-search engine and query expansion, and provide a toolkit to support it.

We present an approach to build highly adaptable extractor for collecting data from diverse Web sites. This approach uses Graph Model to represent content and structures as well as their various types of features. The generated graph is accompanied by a script in a special language called GQML containing the extraction rules. The running of the script transforms the graph into a specified format such as XML file that stores data from various Web sites in a uniform format. The experimental results show the presented approach is both effective and efficient.

The explosion of information on the web turns the search for interested information from the web into a great challenge. In this paper, we present a system called Web Data Engine-SESQ (Search Extract Store Query) that is designed to solve this problem by integrating database techniques with search engine techniques. In contrast with traditional database systems and searching engines, SESQ is different in data model, query expression, data storage schema and the use of index.

When the relational storage method is adopted in the data warehouse system, the most time-consuming operations in OLAP query are multitable join and group-by aggregation. Based on the characteristics of the data warehouse itself and the applications run on it, one new multi-table join algorithm -- Mjoin is given in this paper. And the performance of this new Mjoin algorithm is improved greatly, compared with other traditional multitable join algorithms. In this paper, a new sorting based group-by aggregation algorithm -- MuSA is also given, based on the Mjoin algorithm. The speed of sorting is remarkably improved in this new sorting based aggregation algorithm, as the keyword mapping technology is used to compress the sort keywords in the course of sorting.