Isolation Levels (IL) act as correct contracts between applications and database management systems (DBMSs). The complex code logic and concurrent interactions among transactions make it a hard problem to expose violations of various ILs stated by DBMSs. With the recent proliferation of new DBMSs, especially the cloud ones, there is an urgent demand for a general way to detect bugs violating various ILs. The core challenges come from the requirements of: (a) lightweight (verifying without modifying the application logic in workloads and the source code of DBMSs), (b) generality (verifying various ILs), and (c) efficiency (performing efficient verification on a long running workload). To this end, we propose a powerful and practical bug-finding toolLeopard. For lightweight, we propose to infer transaction dependencies based on the time intervals of operations collected from the client-side, without modifying the source code of DBMSs. For generality, based on a thorough analysis of existing concurrency control protocols, we summarize and abstract four mechanisms which can implement ILs in all commercial DBMSs we have investigated. For efficiency, we design atwo-level pipelineto organize and sort massive time intervals in a time and memory conservative way; we propose amechanism-mirrored verificationto simulate the concurrency control protocols implemented in DBMSs for high throughputs; From experimental results,Leopardoutperforms existing methodsCobraandElle. In practice,Leopardhas a superpower to verify various ILs on any workload running on all commercial DBMSs. Moreover, it has successfully discovered 49 bugs that cannot be found by other existing methods.

Cardinality Estimation (CardEst) is crucial for query optimization. Despite the remarkable achievement in DBMS, there is a pressing need to test or tune the work of CardEst. To satisfy the need, we introduce Artemis, a customizable workload generator, which can be used to generate various scenarios with the sensitive features for CardEst, including various data dependencies, complex SQL structures, and diverse cardinalities. It designs a PK-oriented deterministic data generation mechanism to plot various data characteristics; a search-based workload generation is proposed for composing queries with various complexities; it takes a constraint optimization-guided way to achieve a cost-effective cardinality calculation. In this demonstration, users can explore the core features of Artemis in generating workloads.

Various physical design (PD) options within a single database have emerged to optimize diverse workloads, including row-based PDs (e.g., index) and column-based PDs (e.g., column-store replica), each with its own acceleration advantages for different workloads. Determining the optimal combination of these two PDs is a labor-intensive and challenging task, yet it could result in significant performance improvements for the system. Recent automated index advisors (AIAs) have concentrated on identifying the most advantageous combination of row-based PDs. However, the extension of these efforts to the present problem has proven challenging due to 1) the larger search space of hybrid PD selections, 2) the inadequate consideration of the complex interactions between heterogeneous PDs, and 3) the inaccurate evaluation made by the what-if optimizer. To address these issues, we propose a Hybrid physical design advisor (Hyper) with multi-agent reinforcement learning. Hyper excels at recommending the optimal combination of PDs under any specific workload, with an overarching emphasis on both efficiency and quality. Comprehensive evaluations on well-established benchmarks show that our approach outperforms state-of-the-art methods.

The large language model (LLM)-based knob tuning method has attracted considerable attention due to its excellent in-context learning ability and generalizability. However, the existing LLM-based tuning methods do not effectively harmonize multi-source external knowledge, leading to missed opportunities for enhanced knob tuning. In light of this, we propose Rabbit, a novel approach that leverages Retrieval-augmented generation to enhance database knob tuning tools, which seamlessly integrates structured historical tuning experience with graph-encoded static knowledge. First, we introduce an experience-driven knob selection strategy, enhanced by dependency-aware external knowledge integration, to systematically select key knobs. Second, we develop a cutting-edge multi-agent knob domain pruning method, which ensures the reduced search space remains compact yet effective. Finally, we leverage the few-shot capabilities of LLMs to act as surrogate models, enabling rapid exploration of the pruned search space, followed by incremental optimization that expands the search space using historical insights. Moreover, we also design an adaptive strategy to transition between these two search spaces, striking an optimal balance between exploration and exploitation. Extensive experiments on well-established bench-marks demonstrate that Rabbit outperforms the state-of-the-art methods in both effectiveness and efficiency, pointing to a new paradigm for this area.

Previous learning-based parameter query optimization (PQO) methods excel in static workloads by precisely selecting optimal plans in a cache with a fixed set of representative plans. However, these methods struggle in dynamic workloads because they cannot predict over dynamically changed plan caches. These queries that fall outside the previously observed query parameter distribution have the risk of reusing suboptimal plans. Unlike traditional PQO methods that learn mappings from parametric query parameters to a fixed set of execution plans, our adaptive PQO framework ( APQO ) takes both query parameters and the plans themselves as model inputs, thereby handling variable numbers of plans in dynamic workloads. By embedding plan representations through representation learning, we pre-train a foundation model offline, enabling APQO to acquire a generalizable plan performance prediction model. Leveraging the foundation model's predictive capability along with a hybrid data augmentation strategy, we train an online calibration model with minimal training data for distribution-shifted new queries, rapidly adapting knowledge for reusing new plans. APQO is natively designed to handle the characteristics of dynamic workloads. Experimental results show that APQO outperforms existing PQO methods in dynamic workloads, achieving a higher cache hit ratio and significantly reducing query latency.

To optimize query parallelism techniques, substantial workloads are required with specific query plans and customized output size for each operator (denoted as cardinality constraint). To this end, a rich body of query-aware database generators (QAG) are proposed. However, the complex data dependencies hidden behind queries make previous QAGs suffer from deficiencies in supporting complex operators and controlling the generation errors. In this paper, we design a new generator Mirage supporting well for complex operators with low error bounds for cardinality constraints. First, Mirage leverages Query Rewriting and Set Transforming Rules to decouple dependencies between key and non-key columns, which could help generate each of them individually. Then, for the non-key columns, Mirage abstracts cardinality constraints of operators as placement requirements within each column's domain, and further models the generation problem as a classic bin packing problem. Finally, for the key columns, Mirage proposes a uniform representation of join cardinality constraints for all types of PK-FK joins and partitions the data according to the matching status between PK and F K columns. Then, it formulates the key population as a Constraint Programming problem, which can be solved by an existing CP Solver. The experiments show that Mirage conquers all previous work in either operator support or generation error.

Functionalities of a database system are co-designed and jointly maintain the database performance. Each function-ality usually has its own metrics to evaluate its state. Previous knobs tuning methods regard the database system as a black box and aim to automatically find the optimal configurations by collecting and observing the overall performance data (e.g., transaction throughput per second) under various configuration knobs. However, if a functionality is not running in the tuning phase, its knobs irrelevant to performance changes can also be tuned by existing tools and potential risks would be introduced. To resolve this problem, we design a database knob tuning framework to support functionality-aware knobs tuning. It uses multitask learning to take the database overall performance as the objective of main learning task, and each function module as a separate learning task. This framework enhances the tuning results through learning the relationships between different tasks, and avoids adjusting irrelevant knobs by perceiving the status of functionalities. We validate its generalizability on OceanBase and PostgreSQL. Experimental results show that better performances were achieved on the overall performance and the metrics of various functionalities.

Isolation level (IL) acts as a correctness contract between applications and DBMSs. Problematic IL implementations would cause incorrect transaction execution results and erroneous database states. However, existing studies could not efficiently generate various effective workloads for IL test. The core challenges come from the requirements of (a) black-box testing (trigger the IL code of a closed source DBMS), (b) effective testing (evade redundant and ineffective testing), and (c) anomaly-sensitive testing (test various ILs in a distinguishable way). For black-box testing, we investigate the IL implementations of 15 popular DBMSs and discover that they follow a generic framework that utilizes conflict graphs to manage all conflicts of a workload, and performs a verification policy to prevent non-serializable anomalies. For effective testing, we propose a lightweight data state mirroring method, which helps generate SQL operations that precisely access its expected records and participate the formation of specific conflict graphs. We also propose an efficient history-independent approach to generate dissimilar conflict graphs. It guarantees the graph generation overhead is irrelevant to the scale of historical graphs. For anomaly-sensitive testing, we propose an implantation-based approach to orchestrate conflict record accesses and inject them into different transactions according to the anomaly definition. Our approach outperforms existing approaches in testing effectiveness, efficiency, and coverage. Practically, we have successfully found 33 bugs in popular DBMSs.

Generating synthetic workloads is essential and critical to the performance evaluation of database systems. When benchmarking database performance for a specific application, the similarity between synthetic workloads and real application workloads determines the credibility of the evaluation results. However, it meets a great challenge to catch workload characteristics for a target online transaction processing (OLTP) application considering the complexity of transaction executions. To address this problem, we propose a workload duplicator (Lauca) that can generate synthetic workloads with highly similar performance metrics compared to a specific application on both centralized and distributed databases. By carefully studying the application-driven workload generation problem, we presentTransaction Logic,Data Access DistributionandPartition Access Distributionto characterize runtime workloads and propose novel generation algorithms to guarantee the high fidelity of synthetic workloads. To the best of our knowledge, Lauca is the first application-driven transactional workload generator. We conduct extensive experiments based on TPC-C, SmallBank and YCSB on both centralized and distributed databases. The experimental results show that Lauca consistently generates high-quality synthetic workloads.

The log-structured merge tree (LSM-tree) has been widely adopted as a backbone of modern key-value stores. However, the multiple exponentially increased levels of LSM-tree makes it suffer from high write amplification. Existing studies often improve the write performance by sacrificing the read performance, which is inefficient to make trade-offs between the update and search efficiency. In this paper, we exploit nonvolatile memory (NVM) to address the write amplification issue for systems with NVM-SSD hybrid storage, and further propose a reinforcement learning method to navigate between update and search efficiency on the varying workloads. Specifically, we first propose a lightweight hot data identification method to efficiently capture access recency as well as frequency in NVM with relative large capacity. On this basis, we can eliminate different versions of frequently updated data in high-performance NVM without pushing them to SSD. To improve the data access locality and facilitate fine-grained index tuning in each level, we devise a virtual-split method to partition the key space gradually without extra write amplification. Finally, we propose a cost based Q-learning algorithm to adaptively tune the data organizations of each partition according to the changing access patterns. Experimental results show that our approach outperforms existing methods by up to 2.67×.

Isolation Levels (IL) act as correct contracts between applications and database management systems (DBMSs). The complex code logic and concurrent interactions among transactions make it a hard problem to expose violations of various ILs stated by DBMSs. With the recent proliferation of new DBMSs, especially the cloud ones, there is an urgent demand for a general way to verify various ILs. The core challenges come from the requirements of: (a) lightweight (verifying without modifying the application logic in workloads and the source code of DBMSs), (b) generality (verifying various ILs), and (c) efficiency (performing efficient verification on a long running workload). For lightweight, we propose to deduce transaction dependencies based on time intervals of operations collected from client-sides without touching the source code of DBMSs. For generality, based on a thorough analysis of existing concurrency control protocols, we summarize and abstract four mechanisms which can implement ILs in all commercial DBMSs we have investigated. For efficiency, we design a two-level pipeline to organize and sort massive time intervals in a time and memory conservative way; we propose a mechanism-mirrored verification to simulate the concurrency control protocols implemented in DBMSs for high throughputs. Leopard outperforms existing methods by up to 114× in verification time with a relative small memory usage. In practice, Leopard has a superpower to verify various ILs on any workload running on all commercial DBMSs. Moreover, it has successfully discovered 23 bugs that cannot be found by other existing methods.

Query-aware synthetic data generation is an essential and highly challenging task, important for database management system (DBMS) testing, database application testing and application-driven benchmarking. Prior studies on query-aware data generation suffer common problems of limited parallelization, poor scalability, and excessive memory consumption, making these systems unsatisfactory to terabyte scale data generation. In order to fill the gap between the existing data generation techniques and the emerging demands of enormous query-aware test databases, we design and implement a new data generator, called Touchstone. Touchstone adopts the random sampling algorithm instantiating query parameters and the new data generation schema generating the test database, to achieve fully parallel data generation, linear scalability and austere memory consumption. It has full support of outer joins as well as non-equi-joins for application-oriented data generation. Our experimental results show that Touchstone consistently outperforms the state-of-the-art solution on TPC-H workload by a 1000 speedup without sacrificing simulation fidelity.

Generating synthetic workloads is essential and critical to performance evaluation of database systems. When evaluating database performance for a specific application, the similarity between synthetic workloads and real application workloads determines the credibility of the evaluation results. However, it meets a great challenge to catch workload characteristics with respect to a target application considering the complexity of transaction executions. To address this problem, we propose a workload duplicator (Lauca) that can generate synthetic workloads with highly similar performance metrics compared to the real workloads of a specific application. By carefully studying the application-oriented workload generation problem, we present Transaction Logic and Data Access Distribution to characterize workloads of online transaction processing (OLTP) applications, and propose novel generation algorithms to guarantee the high fidelity of synthetic workloads. To the best of our knowledge, Lauca is the first application-oriented transactional workload generator. We conduct extensive experiments based on TPCC, SmallBank and YCSB on both centralized and distributed databases. The experimental results show that Lauca consistently generates high quality synthetic workloads.

The join operations, including both equi and non-equi joins, are essential to the complex data analytics in the big data era. However, they are not inherently supported by existing DSPEs (Distributed Stream Processing Engines). The state-of-the-art join solutions on DSPEs rely on either complicated routing strategies or resource-inefficient processing structures, which are susceptible to dynamic workload, especially when the DSPEs face various join predicate operations and skewed data distribution. In this paper, we propose a new cost-effective stream join framework, named A-DSP (Adaptive Dimensional Space Processing), which enhances the adaptability of real-time join model and minimizes the resource used over the dynamic workloads. Our proposal includes: 1) a join model generation algorithm devised to adaptively switch between different join schemes so as to minimize the number of processing task required; 2) a load-balancing mechanism which maximizes the processing throughput; and 3) a lightweight algorithm designed for cutting down unnecessary migration cost. Extensive experiments are conducted to compare our proposal against state-of-the-art solutions on both benchmark and real-world workloads. The experimental results verify the effectiveness of our method, especially on reducing the operational cost under pay-as-you-go pricing scheme.

Key-based workload partitioning is now commonly used in parallel stream processing, enabling effective key-value tuple distribution over worker threads in a logical operator. While randomized hashing on the keys is capable of balancing the workload for key-based partitioning when the keys generally follow a static distribution, it is likely to generate poor balancing performance when workload variance occurs on the incoming data stream. This paper presents a new key-based workload partitioning framework, with practical algorithms to support dynamic workload assignment for stateful operators. The framework combines hash-based and explicit key-based routing strategies for workload distribution, which specifies the destination worker threads for a handful of keys and assigns the other keys with the hashing function. We formulate the rebalance operation as an optimization problem, with multiple objectives on minimizing state migration costs, controlling the size of the routing table and breaking workload imbalance among the worker threads. Despite of the NP-hardness nature behind the optimization formulation, we carefully investigate and justify the heuristics behind key (re)routing and state migration, to facilitate fast response to workload variance with ignorable cost to the normal processing in the distributed system. Empirical studies on synthetic data and real-world stream applications validate the usefulness of our proposals and prove the huge advantage of our approaches over state-of-the-art solutions in the literature.

Key-based workload partitioning is a common strategy used in parallel stream processing engines, enabling effective key-value tuple distribution over worker threads in a logical operator. It is likely to generate poor balancing performance when workload variance occurs on the incoming data stream. This paper presents a new key-based workload partitioning framework, with practical algorithms to support dynamic workload assignment for stateful operators. The framework combines hash-based and explicit key-based routing strategies for workload distribution, which specifies the destination worker threads for a handful of keys and assigns the other keys with the hash function. When short-term distribution fluctuations occur to the incoming data stream, the system adaptively updates the routing table containing the chosen keys, in order to rebalance the workload with minimal migration overhead within the stateful operator. We formulate the rebalance operation as an optimization problem, with multiple objectives on minimizing state migration costs, controlling the size of the routing table and breaking workload imbalance among worker threads. Despite of the NP-hardness nature behind the optimization formulation, we carefully investigate and justify the heuristics behind key (re)routing and state migration, to facilitate fast response to workload variance with ignorable cost to the normal processing in the distributed system. Empirical studies on synthetic data and real-world stream applications validate the usefulness of our proposals.

Topic modeling is nowadays widely used in text archive analytics, to find significant topics in news articles and important aspects of product comments available on the Internet. While statistical approaches, e.g. Latent Dirichlet Allocation (LDA) and its variants, are effective on building topic models on long texts, it remains difficult to identify meaningful topics over short texts, e.g. news titles and social-media messages. With the emergence and prosperity of crowdsourcing platforms, it becomes possible and easier for analytical systems to incorporate human intelligence into text analytics. Different from traditional active learning techniques, the combination of crowdsourcing and machine learning poses new challenges on the design of simple tasks for non-experts to finish in seconds. In this paper, we design a new topic modeling technique, fully exploiting the basic intuitions of humans on short text reading. By requesting human labors to subjectively measure the similarity between short text pairs, the accuracy of the topic modeling algorithms could be greatly enhanced, regardless of the prior used in the graphical model. We present well-designed short text pair selection strategies for crowdsourcing and provide analysis on the convergence property of the inference algorithm. Empirical studies show that our proposed approaches improve the result topics on English tweets and Chinese microblogs, by requesting only a small number of labels from crowd.

Matrix-based scheme (Join-Matrix) can prefectly support distributed stream joins, especially for arbitrary join predicates, because it guarantees any tuples from two streams to meet with each other. However,the dynamics and unpredictability features of stream require quick actions on scheme changing. Otherwise, they may lead to degradation of system throughputs and increament of processing latency with the waste of system resources, such as CPUs and Memories. Since Join-Matrix model has the fixed processing architecture with replicated data, these kinds of adverseness will be magnified. Therefore, it is urgent to find a solution that preserves advantages of Join-Matrix model and promises a good usage to computation resources when it meets scheme changing. In this paper, we propose a cost-effective stream join algorithm, which ensures the adaptability of Join-Matrix but with lower resources consumption. Specifically, a varietal matrix generation algorithm is proposed to generate an irregular matrix scheme for assigning the minimal number of tasks; a lightweight migration algorithm is designed to ensure state migration at a low cost; a complete load balance process framework is described to guarantee the correctness during the scheme changing. We conduct extensive experiments to compare our method with baseline systems on both benchmarks and real-workloads, and explain the results in detail.

The hyperlink structure of Wikipedia forms a rich semantic network connecting entities and concepts, enabling it as a valuable source for knowledge harvesting. Wikipedia, as crowd-sourced data, faces various data quality issues which significantly impacts knowledge systems depending on it as the information source. One such issue occurs when an anchor text in a Wikipage links to a wrong Wikipage, causing the error link problem. While much of previous work has focused on leveraging Wikipedia for entity linking, little has been done to detect error links.

With the prosperity of online services enabled by Web 2.0, huge amount of human generated commentary data are now available on the Internet, covering a wide range of domains on different products. Such comments contain valuable information for other customers, but are usually difficult to utilize due to the lack of common description structure, the complexity of opinion expression and fast growing data volume. Comment-based restaurant summarization is even more challenging than other types of products and services, as users' comments on restaurants are usually mixed with opinions on different dishes but attached with only one overall evaluation score on the whole experience with the restaurants. It is thus crucial to distinguish well-made dishes from other lousy dishes by mining the comment archive, in order to generate meaningful and useful summaries for other potential customers. This paper presents a novel approach to tackle the problem of restaurant comment summarization, with a core technique on the new bilateral topic analysis model on the commentary text data. In the bilateral topic model, the attributes discussed in the comments on the dishes and the user's evaluation on the attributes are considered as two independent dimensions in the latent space. Combined with new opinionated word extraction and clustering-based representation selection algorithms, our new analysis technique is effective to generate high-quality summary using representative snippets from the text comments. We evaluate our proposals on two real-world comment archives crawled from the most popular English and Chinese online restaurant review web sites, Yelp and Dianping. The experimental results verify the huge margin of advantage of our proposals on the summarization quality over baseline approaches in the literature.

Customer reviews written at online shopping sites greatly influence the decision of potential buyers. Since existence of noise in reviews is inevitable, helping users alleviate the influence of these noisy reviews has become a fundamental issue for improving service quality in e-commerce transactions, especially for C2C (customer-to-customer) sites. In this paper, we present an approach to reduce the influence of noisy review and improve product ranking quality by using customer credibility. Customer credibility is used to measure to what degree the reviews can be trusted. A feedback strategy is designed to calculate the customer credibility, which relies on the consistency evaluation between individual reviews and overall reviews. Additionally, we provide a method to eliminate the inconsistency problem between the review comments and customer given scores, captured by the learned model on the training data that is constructed automatically. The final product scores are calculated by considering both the customer credibility and the predicted scores. The experimental results on real-world data sets show that our proposed approach provides better products ranking than baseline systems.

The popularity of internet usage greatly motivates the online advertising activities. Compared to advertising on traditional media, online advertising has rich information as well as necessary techniques to achieve precise user targeting. This rich information includes the search behaviors of a user, such as queries issued, or the ads clicked by the user. For popular websites with large number of active users, ad delivery targeting at individual users puts too much burden on the system. User segmentation is an alternative way to relieve this burden by grouping users of similar interests together, then the ad delivery system targets the user segments to display relevant ads, instead of individual users. Existing user segmentation work either adapts clustering methods without considering the hidden semantics embedded in the data, such as K-means, or treats users as data instance and clusters users indirectly even if the latent semantics is incorporated into the transformed data, such as PLSA or LDA. In this paper, we present a search behavior based latent semantic user segmentation method and validate its effectiveness on new ads. Instead of treating users as data instances, they are used as attributes of user issued queries or clicked ads which are considered to be data instances. LDA is then applied to this data set to directly obtain the user segments. Compared to popular K-means clustering, our approach achieves higher CTR values on new ads, with only simple search information.

For graph-based dependency parsing, how to enrich high-order features without increasing decoding complexity is a very challenging problem. To solve this problem, this paper presents an approach to representing high-order features for graph-based dependency parsing models using a dependency language model and beam search. Firstly, we use a baseline parser to parse a large-amount of unannotated data. Then we build the dependency language model (DLM) on the auto-parsed data. A set of new features is represented based on the DLM. Finally, we integrate the DLM-based features into the parsing model during decoding by beam search. We also utilize the features in bilingual text (bitext) parsing models. The main advantages of our approach are: 1) we utilize rich high-order features defined over a view of large scope and additional large raw corpus; 2) our approach does not increase the decoding complexity. We evaluate the proposed approach on the monotext and bitext parsing tasks. In the monotext parsing task, we conduct the experiments on Chinese and English data. The experimental results show that our new parser achieves the best accuracy on the Chinese data and comparable accuracy with the best known systems on the English data. In the bitext parsing task, we conduct the experiments on a Chinese-English bilingual data and our score is the best reported so far.

A fundamental issue for C2C transactions is how to rank the products based on the reviews written by the previous customers. In this paper, we present an approach to improve products ranking by tackling the noisy ratings that exist in the practical systems. The first problem is the credibility of the customers. We design an iterative algorithm to measure the customer credibility. In the algorithm, we use a feedback strategy to increase or decrease the customer credibility. We increase the credibility for a customer if the customer gives a high (low) score to a good (bad) product and decrease the value if the customer gives a low (high) score to a good (bad) product. The second problem is the inconsistency between the review comments and scores. To deal with it, we train a classifier on a training data that is constructed automatically. The trained classifier is used to predict the scores of the comments. Finally, we calculate the scores of products by considering the customer credibility and the predicted scores. The experimental results show that our proposed approach provides better products ranking than the baseline systems.

We introduce COSTA, for content-based search using term aggregation. Besides advantages shared with other P2P-based information retrieval systems, the system has several characteristics that distinguish itself from other systems: First, an adaptive indexing scheme which can dynamically identify important terms is used. Important terms are indexed in a chord-like ring, while other terms are aggregated in a balanced tree. We argue that this architecture is more flexible and suitable for term indexing than DHT-based methods. Furthermore, this structure allows to eliminate the requirement of maintaining global knowledge, and hence we can avoid the difficulty in maintaining such knowledge. Term aggregation is useful not only for performance enhancement, but also for improving the quality of search, by using of the term statistics information obtained via the aggregation. Traditional IR techniques such as query expansion can be utilized based on the information. Therefore, COSTA finely integrates distributed indexing with information retrieval. Advanced techniques, such as node clustering, caching and workload balance, are employed. We show that more existing optimization techniques can be adopted for further improvement of the system's performance.

Multi-dimensional data indexing has received much attention in a centralized database. However, not so much work has been done on this topic in the context of Peerto- Peer systems. In this paper, we propose a new Peer-to- Peer framework based on a balanced tree structure overlay, which can support extensible centralized mapping methods and query processing based on a variety of multidimensional tree structures, including R-Tree, X-Tree, SSTree, and M-Tree. Specifically, in a network with N nodes, our framework guarantees that point queries and range queries can be answered within O(logN) hops. We also provide an effective load balancing strategy to allow nodes to balance their work load efficiently. An experimental assessment validates the practicality of our proposal.

Peer-to-Peer systems have recently become a popular means to share resources. Effective search is a critical requirement in such systems, and a number of distributed search structures have been proposed in the literature. Most of these structures provide "log time search" capability, where the logarithm is taken base 2. That is, in a system with N nodes, the cost of the search is O(log2N).In database systems, the importance of large fanout index structures has been well recognized. In P2P search too, the cost could be reduced considerably if this logarithm were taken to a larger base. In this paper, we propose a multi-way tree search structure, which reduces the cost of search to O(logmN), where m is the fanout. The penalty paid is a larger update cost, but we show how to keep this penalty to be no worse than linear in m. We experimentally explore this tradeoff between search and update cost as a function of m, and suggest how to find a good trade-off point.The multi-way tree structure we propose, BATON*, is derived from the BATON structure that has recently been suggested. In addition to multi-way fanout, BATON* also adds support for multi-attribute queries to BATON.