waashk/dblp huggingface dataset:
a formal characterization of pivot/unpivot. pivot is an important relational operation that allows data in rows to be exchanged for columns. although most current relational database management systems support pivot-type operations, to date a purely formal, algebraic characterization of pivot has been lacking. in this paper, we present a characterization in terms of extended relational algebra operators τ (transpose), π (drop projection), and μ (unique optimal tuple merge). this enables us to (1) draw parallels with pivot and existing operators employed in dynamic data mapping systems (ddms), (2) formally characterize invertible pivot instances, and (3) provide complexity results for pivot-type operations. these contributions are an important part of ongoing work on formal models for relational olap.
estimating average precision with incomplete and imperfect judgments. we consider the problem of evaluating retrieval systems using incomplete judgment information. buckley and voorhees recently demonstrated that retrieval systems can be efficiently and effectively evaluated using incomplete judgments via the bpref measure [6]. when relevance judgments are complete, the value of bpref is an approximation to the value of average precision using complete judgments. however, when relevance judgments are incomplete, the value of bpref deviates from this value, though it continues to rank systems in a manner similar to average precision evaluated with a complete judgment set. in this work, we propose three evaluation measures that (1) are approximations to average precision even when the relevance judgments are incomplete and (2) are more robust to incomplete or imperfect relevance judgments than bpref. the proposed estimates of average precision are simple and accurate, and we demonstrate the utility of these estimates using trec data.
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.
erknn: efficient reverse k-nearest neighbors retrieval with local knn-distance estimation. the reverse k-nearest neighbors (rknn) queries are important in profile-based marketing, information retrieval, decision support and data mining systems. however, they are very expensive and existing algorithms are not scalable to queries in high dimensional spaces or of large values of k. this paper describes an efficient estimation-based rknn search algorithm (erknn) which answers rknn queries based on local knn-distance estimation methods. the proposed approach utilizes estimation-based filtering strategy to lower the computation cost of rknn queries. the results of extensive experiments on both synthetic and real life datasets demonstrate that erknn algorithm retrieves rknn efficiently and is scalable with respect to data dimensionality, k, and data size.
dynamic versioning concurrency control for index-based data access in main memory database systems. we present a concurrency control scheme using dynamic versioning for index-based data access in main memory database systems. this scheme enables read-only transactions read correct version without holding any locks or latches, while update transactions only obtain a few locks or latches without deadlocks. efficient version management is designed to support high concurrency level and low space overhead. the interaction between dynamic versioning and indexing is considered so that all available versions can be accessed through indexing. experiment results show that dynamic versioning can improve the performance in concurrent environment significantly.
tracking dragon-hunters with language models. we are interested in the problem of understanding the connections between human activities and the content of textual information generated in regard to those activities. firstly, we define and motivate this problem as an important part in making sense of various life events. secondly, we introduce the domain of massive online collaborative environments, specifically online virtual worlds, where people meet, exchange messages, and perform actions as a rich data source for such an analysis. finally, we outline three experimental tasks and show how statistical language modeling and text clustering techniques may allow us to explore those connections successfully.
slicing*-tree based web page transformation for small displays. we propose a new web page transformation method for browsing on mobile devices with small displays. in our approach, an original web page that does not fit into the screen is transformed into a set of pages, each of which fits into the screen. this transformation is done through slicing the original page. the resulting set of transformed pages form a multi-level tree structure, called a slicing*-tree, in which an internal node consists of a thumbnail image with hyperlinks and a leaf node is a block from the original web page. our slicing*-tree based web page transformation eases web browsing on small displays by providing screen-fitting visual context and reducing page scrolling effort.
re-ranking search results using query logs. this work addresses two common problems in search, frequently occurring with underspecified user queries: the top-ranked results for such queries may not contain documents relevant to the user's search intent, and fresh and relevant pages may not get high ranks for an underspecified query due to their freshness and to the large number of pages that match the query, despite the fact that a large number of users have searched for parts of their content recently. we propose a novel method, q-rank, to effectively refine the ranking of search results for any given query by constructing the query context from search query logs. evaluation results show that q-rank gains a considerable advantage over the current ranking system of a large-scale commercial web search engine, being able to improve the relevance of search results for 82% of the queries.
supporting ranked search in parallel search cluster networks. we investigate how to support ranked keyword search in a parallel search cluster network, which is a newly proposed peer-to-peer network overlay. in particular, we study how to efficiently acquire and distribute the global information required by ranked keyword search by taking advantage of the architectural features of pscns.
amnesic online synopses for moving objects. we present a hierarchical tree structure for online maintenance of time-decaying synopses over streaming data. we exemplify such an amnesic behavior over streams of locations taken from numerous moving objects in order to obtain reliable trajectory approximations as well as affordable estimates regarding distinct count spatiotemporal queries.
privacy leakage in multi-relational databases via pattern based semi-supervised learning. in multi-relational databases, a view, which is a context- and content-dependent subset of one or more tables (or other views), is often used to preserve privacy by hiding sensitive information. however, recent developments in data mining present a new challenge for database security even when traditional database security techniques, such as database access control, are employed. this paper presents a data mining framework using semi-supervised learning that demonstrates the potential for privacy leakage in multi-relational databases. many different types of semi-supervised learning techniques, such as the k-nearest neighbor (knn) method, can be used to demonstrate privacy leakage. however, we also introduce a new approach to semi-supervised learning, hyperclique pattern based semi-supervised learning (hpsl), which differs from traditional semi-supervised learning approaches in that it considers the similarity among groups of objects instead of only pairs of objects. our experimental results show that both the knn and hpsl methods have the ability to compromise database security, although hpsl is better at this privacy violation than the knn method.
designing semantics-preserving cluster representatives for scientific input conditions. in scientific domains, knowledge is often discovered from experiments by grouping or clustering them based on the similarity of their output. the causes of similarity are analyzed based on the input conditions characterizing a given type of output, i.e., a given cluster. this analysis helps in applications such as decision support in industry. cluster representatives form at-a-glance depictions for such applications. randomly selecting a set of conditions in a cluster as its representative is not sufficient since distinct combinations of inputs could lead to the same cluster. in this paper, an approach called descond is proposed to design semantics-preserving cluster representatives for scientific input conditions. we define a notion of distance for conditions to capture semantics based on the types of their attributes and their relative importance. using this distance, methods of building candidate cluster representatives with different levels of detail are proposed. candidates are compared using the descond encoding proposed in this paper that assesses their complexity and information loss, given user interests. the candidate with the lowest encoding for each cluster is returned as its designed representative. descond is evaluated with real data from materials science. evaluation with domain expert interviews and formal user surveys shows that designed representatives consistently outperform randomly selected ones and different candidates suit different users.
pruning strategies for mixed-mode querying. web information retrieval systems face a range of unique challenges, not the least of which is the sheer scale of the data that must be handled. also specific to web retrieval is that queries may be a mix of boolean and ranked features, and documents may have static score components that must also be factored into the ranking process. in this paper we consider a range of query semantics used in web retrieval systems, and show that impact-sorted indexes provide support for dynamic pruning mechanisms and in doing so allow fast document-at-a-time resolution of typical mixed-mode queries, even on relatively large volumes of data. our techniques also extend to more complex query semantics, including the use of phrase, proximity, and structural constraints.
structure-based querying of proteins using wavelets. the ability to retrieve molecules based on structural similarity has use in many applications, from disease diagnosis and treatment to drug discovery and design. in this paper, we present a method to represent protein molecules that allows for the fast, flexible and efficient retrieval of similar structures, based on either global or local attributes. we begin by computing the pair-wise distance between amino acids, transforming each 3d structure into a 2d distance matrix. we normalize this matrix to a specific size and apply a 2d wavelet decomposition to generate a set of approximation coefficients, which serves as our global feature vector. this transformation reduces the overall dimensionality of the data while still preserving spatial features and correlations. we test our method by running queries on three different protein data sets that have been used previously in the literature, basing our comparisons on labels taken from the scop database. we find that our method significantly outperforms existing approaches, in terms of retrieval accuracy, memory utilization and execution time. specifically, using a k-d tree and running a 10-nearest-neighbor search on a dataset of 33,000 proteins against itself, we see an average accuracy of 89% at the scop superfamily level and a total query time that is up to 350 times faster than previously published techniques. in addition to processing queries based on global similarity, we also propose innovative extensions to effectively match proteins based solely on shared local substructures, allowing for a more flexible query interface.
optimizing web search using web click-through data. the performance of web search engines may often deteriorate due to the diversity and noisy information contained within web pages. user click-through data can be used to introduce more accurate description (metadata) for web pages, and to improve the search performance. however, noise and incompleteness, sparseness, and the volatility of web pages and queries are three major challenges for research work on user click-through log mining. in this paper, we propose a novel iterative reinforced algorithm to utilize the user click-through data to improve search performance. the algorithm fully explores the interrelations between queries and web pages, and effectively finds "virtual queries" for web pages and overcomes the challenges discussed above. experiment results on a large set of msn click-through log data show a significant improvement on search performance over the naive query log mining algorithm as well as the baseline search engine.
cache-oblivious nested-loop joins. we propose to adapt the newly emerged cache-oblivious model to relational query processing. our goal is to automatically achieve an overall performance comparable to that of fine-tuned algorithms on a multi-level memory hierarchy. this automaticity is because cache-oblivious algorithms assume no knowledge about any specific parameter values, such as the capacity and block size of each level of the hierarchy. as a first step, we propose recursive partitioning to implement cache-oblivious nested-loop joins (nljs) without indexes, and recursive clustering and buffering to implement cache-oblivious nljs with indexes. our theoretical results and empirical evaluation on three different architectures show that our cache-oblivious nljs match the performance of their manually optimized, cache-conscious counterparts.
generating concise association rules. association rule mining has made many achievements in the area of knowledge discovery. however, the quality of the extracted association rules is a big concern. one problem with the quality of the extracted association rules is the huge size of the extracted rule set. as a matter of fact, very often tens of thousands of association rules are extracted among which many are redundant thus useless. mining non-redundant rules is a promising approach to solve this problem. the min-max exact basis proposed by pasquier et al [pasquier05] has showed exciting results by generating only non-redundant rules. in this paper, we first propose a relaxing definition for redundancy under which the min-max exact basis still contains redundant rules; then we propose a condensed representation called reliable exact basis for exact association rules. the rules in the reliable exact basis are not only non-redundant but also more succinct than the rules in min-max exact basis. we prove that the redundancy eliminated by the reliable exact basis does not reduce the belief to the reliable exact basis. the size of the reliable exact basis is much smaller than that of the min-max exact basis. moreover, we prove that all exact association rules can be deduced from the reliable exact basis. therefore the reliable exact basis is a lossless representation of exact association rules. experimental results show that the reliable exact basis significantly reduces the number of non-redundant rules.
mrssa: an iterative algorithm for similarity spreading over interrelated objects. we introduce the multiple relationship similarity spreading algorithm (mrssa) to enhance ir effectiveness. this method has similarity computed in an iterative "spreading" fashion for multiple object types, combining both inter- and intra-object relationships. we demonstrate the value of this approach in the context of the www, where the key objects are web pages and queries, relationships considered are derived from hyperlinks (in- and out-links) and click-through logs.
mining coherent patterns from heterogeneous microarray data. microarray technology is a powerful tool for geneticists to monitor interactions among tens of thousands of genes simultaneously. there has been extensive research on coherent subspace clustering of gene expressions measured under consistent experimental settings. however, these methods assume that all experiments are run using the same batch of microarray chips with similar characteristics of noise. algorithms developed under this assumption may not be applicable for analyzing data collected from heterogeneous settings, where the set of genes being monitored may be different and expression levels may be not directly comparable even for the same gene. in this paper, we propose a model, f-cluster, for mining subspace coherent patterns from heterogeneous gene expression data. we compare our model with previously proposed models. we analyze the search space of the problem and give a naïve solution for it.
describing differences between databases. we study the novel problem of efficiently computing the update distance for a pair of relational databases. in analogy to the edit distance of strings, we define the update distance of two databases as the minimal number of set-oriented insert, delete and modification operations necessary to transform one database into the other. we show how this distance can be computed by traversing a search space of database instances connected by update operations. this insight leads to a family of algorithms that compute the update distance or approximations of it. in our experiments we observed that a simple heuristic performs surprisingly well in most considered cases.our motivation for studying distance measures for databases stems from the field of scientific databases. there, replicas of a single database are often maintained at different sites, which typically leads to (accidental or planned) divergence of their content. to re-create a consistent view, these differences must be resolved. such an effort requires an understanding of the process that produced them. we found that minimal update sequences of set-oriented update operations are a proper and concise representation of systematic errors, thus giving valuable clues to domain experts responsible for conflict resolution.
a probabilistic relevance propagation model for hypertext retrieval. a major challenge in developing models for hypertext retrieval is to effectively combine content information with the link structure available in hypertext collections. although several link-based ranking methods have been developed to improve retrieval results, none of them can fully exploit the discrimination power of contents as well as fully exploit all useful link structures. in this paper, we propose a general relevance propagation framework for combining content and link information. the framework gives a probabilistic score to each document defined based on a probabilistic surfing model. two main characteristics of our framework are our probabilistic view on the relevance propagation model and propagation through multiple sets of neighbors. we compare eight different models derived from the probabilistic relevance propagation framework on two standard trec web test collections. our results show that all the eight relevance propagation models can outperform the baseline content only ranking method for a wide range of parameter values, indicating that the relevance propagation framework provides a general, effective and robust way of exploiting link information. our experiments also show that using multiple neighbor sets outperforms using just one type of neighbors significantly and taking a probabilistic view of propagation provides guidance on setting propagation parameters.
virtual cursors for xml joins. structural joins are a fundamental operation in xml query processing and a large body of work has focused on index-based algorithms for executing them. in this paper, we describe how two well-known index features -- path indices and ancestor information -- can be combined in a novel way to replace one or more of the physical index cursors in a structural join with <i>virtual cursors</i>. the position of a virtual cursor is derived from the path and ancestor information of a physical cursor. implementation results are provided to show that, by eliminating index i/o, virtual cursors can improve the performance of structural joins by an order of magnitude or more.
topic evolution and social interactions: how authors effect research. we propose a method for discovering the dependency relationships between the topics of documents shared in social networks using the latent social interactions, attempting to answer the question: given a seemingly new topic, from where does this topic evolve? in particular, we seek to discover the pair-wise probabilistic dependency in topics of documents which associate social actors from a latent social network, where these documents are being shared. by viewing the evolution of topics as a markov chain, we estimate a markov transition matrix of topics by leveraging social interactions and topic semantics. metastable states in a markov chain are applied to the clustering of topics. applied to the citeseer dataset, a collection of documents in academia, we show the trends of research topics, how research topics are related and which are stable. we also show how certain social actors, authors, impact these topics and propose new ways for evaluating author impact.
cooperative caching for k-nn search in ad hoc networks. mobile ad hoc networks have multiple limitations in performing similarity-based nearest neighbor search - dynamic topology, frequent disconnections, limited power, and restricted bandwidth. cooperative caching is an effective technique to reduce network traffic and increase accessibility. in this paper, we propose to solve the k-nearest-neighbor search problem in ad hoc networks using a semantic-based caching scheme which reflects the content distribution in the network. the proposed scheme describes the semantic similarity among data objects using constraints, and employs cooperative caching to estimate the content distribution in the network. the query resolution based on the cooperative caching scheme is non-flooding and hierarchy-free.
voting for candidates: adapting data fusion techniques for an expert search task. in an expert search task, the users' need is to identify people who have relevant expertise to a topic of interest. an expert search system predicts and ranks the expertise of a set of candidate persons with respect to the users' query. in this paper, we propose a novel approach for predicting and ranking candidate expertise with respect to a query. we see the problem of ranking experts as a voting problem, which we model by adapting eleven data fusion techniques.we investigate the effectiveness of the voting approach and the associated data fusion techniques across a range of document weighting models, in the context of the trec 2005 enterprise track. the evaluation results show that the voting paradigm is very effective, without using any collection specific heuristics. moreover, we show that improving the quality of the underlying document representation can significantly improve the retrieval performance of the data fusion techniques on an expert search task. in particular, we demonstrate that applying field-based weighting models improves the ranking of candidates. finally, we demonstrate that the relative performance of the adapted data fusion techniques for the proposed approach is stable regardless of the used weighting models.