The trajectories of RFID tags can be modeled as a set of time-parameterized line segments defined by two tag events, namely entering and leaving a specific location. Each tag interval (TI) is specified in a three-dimensional domain, with axes: Tag IDentifier (TID), Location IDentifier (LID), and time (TIME). The query performance for tracing tags depends on the distribution of the TIs in the data space. We investigate a more efficient representation of TIs, which orders the set of values in the three-dimensional domain. Our analysis shows that the ordering of LIDs makes a greater contribution to the efficiency of query processing than TID or TIME. To execute queries efficiently, an optimal ordering of LIDs is important. To solve this problem, we propose a new LID proximity function for reordering an arbitrary LID ordering. We also propose a reordering scheme for LIDs to determine an optimal sequence of LIDs in the domain. Our experiments show that the proposed reordering scheme considerably improves the performance of queries for tracing tag locations, compared with previous methods for assigning LIDs.