A Local-Pattern Related Look-Up Table

• URL: http://arxiv.org/abs/2212.13922v1
• Date: Thu, 22 Dec 2022 06:02:13 GMT
• Title: A Local-Pattern Related Look-Up Table
• Authors: Chung-Chin Shih, Ting Han Wei, Ti-Rong Wu, and I-Chen Wu
• Abstract summary: A Relevance-Zone pattern table (RZT) can be used to replace a traditional transposition table. RZS is the current state-of-the-art in solving L&D problems in Go. The overhead of traversing the radix tree in practice during lookup remain flat logarithmically in relation to the number of entries stored in the table.
• Score: 9.260657061050887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper describes a Relevance-Zone pattern table (RZT) that can be used to replace a traditional transposition table. An RZT stores exact game values for patterns that are discovered during a Relevance-Zone-Based Search (RZS), which is the current state-of-the-art in solving L&D problems in Go. Positions that share the same pattern can reuse the same exact game value in the RZT. The pattern matching scheme for RZTs is implemented using a radix tree, taking into consideration patterns with different shapes. To improve the efficiency of table lookups, we designed a heuristic that prevents redundant lookups. The heuristic can safely skip previously queried patterns for a given position, reducing the overhead to 10% of the original cost. We also analyze the time complexity of the RZT both theoretically and empirically. Experiments show the overhead of traversing the radix tree in practice during lookup remain flat logarithmically in relation to the number of entries stored in the table. Experiments also show that the use of an RZT instead of a traditional transposition table significantly reduces the number of searched nodes on two data sets of 7x7 and 19x19 L&D Go problems.

Related papers

• TableRAG: Million-Token Table Understanding with Language Models [53.039560091592215]
  TableRAG is a Retrieval-Augmented Generation (RAG) framework specifically designed for LM-based table understanding. TableRAG leverages query expansion combined with schema and cell retrieval to pinpoint crucial information before providing it to the LMs. Our results demonstrate that TableRAG achieves the highest retrieval quality, leading to the new state-of-the-art performance on large-scale table understanding.
  arXiv  Detail & Related papers  (2024-10-07T04:15:02Z)
• LORE++: Logical Location Regression Network for Table Structure Recognition with Pre-training [45.80561537971478]
  Table structure recognition (TSR) aims at extracting tables in images into machine-understandable formats. We model TSR as a logical location regression problem and propose a new TSR framework called LORE. Our proposed LORE is conceptually simpler, easier to train, and more accurate than other paradigms of TSR.
  arXiv  Detail & Related papers  (2024-01-03T03:14:55Z)
• Learning Recurrent Models with Temporally Local Rules [0.0]
  We show how a generative model can learn the joint distribution over current and previous states, rather than merely the transition probabilities. We show on toy datasets that different architectures employing this principle can learn aspects of the data typically requiring the backward pass.
  arXiv  Detail & Related papers  (2023-10-20T05:30:30Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQ is a new formulation for scene graph generation that avoids the multi-task learning problem and the entity pair distribution. We employ a DETR-based encoder-decoder conditional queries to significantly reduce the entity label space as well. Experimental results show that TraCQ not only outperforms existing single-stage scene graph generation methods, it also beats many state-of-the-art two-stage methods on the Visual Genome dataset.
  arXiv  Detail & Related papers  (2023-06-09T06:02:01Z)
• Unsupervised Feature Based Algorithms for Time Series Extrinsic Regression [0.9659642285903419]
  Time Series Extrinsic Regression (TSER) involves using a set of training time series to form a predictive model of a continuous response variable. DrCIF and FreshPRINCE models are the only ones that significantly outperform the standard rotation forest regressor.
  arXiv  Detail & Related papers  (2023-05-02T13:58:20Z)
• LORE: Logical Location Regression Network for Table Structure Recognition [24.45544796305824]
  Table structure recognition aims at extracting tables in images into machine-understandable formats. Recent methods solve this problem by predicting the adjacency relations of detected cell boxes. We propose a new TSR framework called LORE, standing for LOgical location REgression network.
  arXiv  Detail & Related papers  (2023-03-07T08:42:46Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Continuous-Time Sequential Recommendation with Temporal Graph Collaborative Transformer [69.0621959845251]
  We propose a new framework Temporal Graph Sequential Recommender (TGSRec) upon our defined continuous-time bi-partite graph. TCT layer can simultaneously capture collaborative signals from both users and items, as well as considering temporal dynamics inside sequential patterns. Empirical results on five datasets show that TGSRec significantly outperforms other baselines.
  arXiv  Detail & Related papers  (2021-08-14T22:50:53Z)
• Large-Scale Spatio-Temporal Person Re-identification: Algorithm and Benchmark [100.77540900932763]
  We contribute a novel Large-scale Spatio-Temporal (LaST) person re-ID dataset, including 10,860 identities with more than 224k images. LaST presents more challenging and high-diversity reID settings, and significantly larger spatial and temporal ranges.
  arXiv  Detail & Related papers  (2021-05-31T16:05:51Z)
• Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game [60.71662712899962]
  Tabu Search (TS) metaheuristic improves simple local search algorithms by enabling the algorithm to escape local optima points. This paper investigates the performance of TS and considers the effects of the size of the Tabu list and the size of the neighbourhood for a procedural content generation.
  arXiv  Detail & Related papers  (2020-06-04T09:15:46Z)
• Increasing the Inference and Learning Speed of Tsetlin Machines with Clause Indexing [9.440900386313215]
  The Tsetlin Machine (TM) is a machine learning algorithm founded on the classical Tsetlin Automaton (TA) and game theory. We report up to 15 times faster classification and three times faster learning on MNIST and Fashion-MNIST image classification, and IMDb sentiment analysis.
  arXiv  Detail & Related papers  (2020-04-07T08:16:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.